package src.tree.medium;

import java.util.LinkedList;
import java.util.Queue;

/**
 * 有 n 个城市，其中一些彼此相连，另一些没有相连。如果城市 a 与城市 b 直接相连，且城市 b 与城市 c 直接相连，那么城市 a 与城市 c 间接相连。
 * <p>
 * 省份 是一组直接或间接相连的城市，组内不含其他没有相连的城市。
 * <p>
 * 给你一个 n x n 的矩阵 isConnected ，其中 isConnected[i][j] = 1 表示第 i 个城市和第 j 个城市直接相连，而 isConnected[i][j] = 0 表示二者不直接相连。
 * <p>
 * 返回矩阵中 省份 的数量。
 * <p>
 *  
 * <p>
 * 示例 1：
 * <p>
 * <p>
 * 输入：isConnected = [[1,1,0],[1,1,0],[0,0,1]]
 * 输出：2
 * 示例 2：
 * <p>
 * <p>
 * 输入：isConnected = [[1,0,0],[0,1,0],[0,0,1]]
 * 输出：3
 * <p>
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode-cn.com/problems/number-of-provinces
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 */
public class NumberOfProvinces {
    public static void main(String[] args) {
        var example1 = new int[][]{{1, 1, 0}, {1, 1, 0}, {0, 0, 1}};
        var example2 = new int[][]{{1, 0, 0}, {0, 1, 0}, {0, 0, 1}};
        var example3 = new int[][]{{1, 0, 0, 1}, {0, 1, 1, 0}, {0, 1, 1, 1}, {1, 0, 1, 1}};
        /*
         * 首先，分析题目，结合二维数组，可以得出，二维数组的主对角线（坐上 -> 右下） 元素一定为 1，且矩阵关于主对角线呈对称。
         *
         * 其次，可知，城市的数量 = 主对角线的元素个数 = 矩阵长度 = 矩阵宽度； 而省份数量 <= 城市数量
         * */
        var i = Solution_DFS.findCircleNum(example3);
        System.out.println(i);

    }
}

/**
 * 深度优先算法
 */
class Solution_DFS {
    static int findCircleNum(int[][] isConnected) {
        // 所以，先定义一个变量 = 城市数量 = 矩阵长度 来控制循环的次数
        int length = isConnected.length;
        // 定义省份数量，默认 = 0
        int provinces = 0;
        // 定义一个数组，保存当前城市（第 0 ~ length 个）是否被访问过
        boolean[] visited = new boolean[length];
        // 循环遍历所有城市
        for (int i = 0; i < length; i++) {
            // 如果当前城市还未被访问
            if (!visited[i]) {
                // 进入 DFS 算法，搜索当前城市的相邻城市
                /* DFS 算法，需要几个参数。
                 *      1： 原数组 isConnected：  因为需要根据这个二维数组判定某两个城市是否相邻
                 *      2： 访问标识 visited：    需要这个数组判定当前城市是否已经访问过，防止重复访问
                 *      3： 当前城市 i       ：   需要从这个城市为起点搜索
                 */
                dfs(isConnected, visited, i);
                // 搜索完毕， 说明当前城市已经没有与其相邻的城市了，这些城市便划分为一个省，省份数量 + 1
                provinces++;
            }
        }
        // 返回最终得到的省份数量
        return provinces;
    }

    static void dfs(int[][] isConnected, boolean[] visited, int i) {
        // 循环所有城市
        for (int j = 0; j < isConnected.length; j++) {
            // 当 i 城市 和 j 城市相邻 且 j 城市还未被访问过时
            if (isConnected[i][j] == 1 && !visited[j]) {
                // 标记 i 城市已访问
                visited[i] = true;
                // 继续以 i 城市为起点深入搜索
                dfs(isConnected, visited, j);
            }
        }
    }
}

/**
 * 广度优先算法
 */
class Solution_BFS {
    static int findCircleNum(int[][] isConnected) {
        // 先定义一个变量 = 城市数量 = 矩阵长度 来控制循环的次数
        int length = isConnected.length;
        // 定义省份数量，默认 = 0
        int provinces = 0;
        // 定义一个数组，保存当前城市（第 0 ~ length 个）是否被访问过
        boolean[] visited = new boolean[length];

        // 定义一个队列
        Queue<Integer> queue = new LinkedList<>();
        // 循环所有城市
        for (int i = 0; i < length; i++) {
            // 如果当前城市没有被访问
            if (!visited[i]) {
                // 将当前城市添加到队列
                queue.offer(i);
                // 循环处理队列元素，直至队列为空
                while (!queue.isEmpty()) {
                    // 依次取出队列元素
                    int j = queue.poll();
                    // 将其标记为已访问
                    visited[j] = true;
                    // 遍历所有城市
                    for (int k = 0; k < length; k++) {
                        // 如果取出的城市与遍历到的城市相邻，且遍历到的这个城市还未访问
                        if (isConnected[j][k] == 1 && !visited[k]) {
                            // 则将其加入队列
                            queue.offer(k);
                        }
                    }
                }
                // 直到队列为空，说明一次搜索结束，这些城市相邻，省份数量 +1，然后继续搜索剩余未被访问的城市
                provinces++;
            }
        }
        return provinces;
    }
}

/**
 * 并查集算法
 */
class Solution_Union {
    // 计算连通分量。如果两个城市之间有关联，则属于同一个连通分量
    static int findCircleNum(int[][] isConnected) {
        // 先定义一个变量 = 城市数量 = 矩阵长度 来控制循环的次数
        int length = isConnected.length;
        // 定义省份数量，默认 = 0
        int provinces = 0;
        // 定义一个数组，保存当前城市的连通分量
        int[] parent = new int[length];

        // 给这个数组赋值，默认值等于城市编号
        for (int i = 0; i < length; i++) {
            parent[i] = i;
        }

        // 遍历所有城市
        for (int i = 0; i < length; i++) {
            // 因为矩阵式关于主对角线对称的，所以只需要遍历左下角或右上角即可
            for (int j = i + 1; j < length; j++) {
                // 如果两个城市是相连的
                if (isConnected[i][j] == 1) {
                    // 合并这两个城市
                    union(parent, i, j);
                }
            }
        }

        // 遍历所有连通分量标识，相同的标识，则说明是同一个省份
        for (int i = 0; i < length; i++) {
            if (parent[i] == i)
                provinces++;
        }

        return provinces;
    }

    // 合并两个城市 i 和 j 并更新他们的连通分量标识
    static void union(int[] parent, int i, int j) {
        parent[find(parent, i)] = find(parent, j);
    }

    // 查找某个城市对应的连通分量的标识
    static int find(int[] parent, int i) {
        if (parent[i] != i) {
            parent[i] = find(parent, parent[i]);
        }
        return parent[i];
    }
}

